Greatest Common Divisor From Factorisation

Note that as written above, we use the same set of primes in the factorisation for each $a$ and $b$. This is just for notational simplicity. Think of $\{p_1,\dots ,p_n\}$ as the set of all primes which divide either $a$ or $b$, and the powers ${\alpha }_i$ or ${\beta }_i$ may be $0$ as necessary.

The idea here is very simple, choosing a power bigger than either ${\alpha }_i$ or ${\beta }_i$ for $p_i$ will result in the result not being a common divisor, however choosing anything smaller than both will not be as big as it can be. Hence we take the minimimum of the corresponding powers.

Proof

This follows from the expression of divisors from the unique factorisation.

That is, some integer $m$ is a divisor of $a$ and $b$ if

where $0\le {\gamma }_i\le {\alpha }_i,{\beta }_i$ for all $i\in \{1,\dots ,n\}$. Since $p_i\ge 2$ for each $p_i$, maximising powers of each $p_i$ results in the greatest integer $m$. As such, to maintain the condition above, we choose ${\gamma }_i=min\{{\alpha }_i,{\beta }_i\}$ for each $i$.